/*
 * Aho corasick test generator
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <unistd.h>

#define SMALLTESTS	20
#define LARGETESTS	60

struct testdata {
	int substr_count;
	char **substrings;
	char *text;
	int text_len;
};

char *
strdup(const char *orig)
{
	char *ret;

	ret = malloc(strlen(orig) + 1UL);
	strcpy(ret, orig);

	return ret;
}

char *
generate_random_string(int alpha, int len)
{
	char *s;
	register int i;

	if (alpha < 1 || alpha > 26 || len < 1)
		return NULL; /* nope, not cool */

	s = malloc(len + 1UL);
	s[len] = '\0';
	for (i = 0; i < len; i++)
		s[i] = rand() % alpha + 'a';

	return s;
}

int
string_hash(char *s, const int alpha)
{
	register int h = 0;

	while (*s) {
		h = (h * 26 + *s) % 1303;
		s++;
	}

	return h;
}

/*
 * storage must be allocated
 */
char *
gen_new_substr(const int chance, const int substr_maxlen, const int alpha,
		struct testdata *test, const int idx, const int ss_type)
{
	char *str;
	int c, i = 0;
	int other_substr;
	char *app;

	str = calloc(substr_maxlen + 1UL, sizeof *str);

	if (ss_type == 0) {
		while (i < substr_maxlen) {
			c = rand();
			if (chance > 0 && (c % 1000) + 1 <= chance && i > 1) {
				/* early ending */
				str[i] = '\0';
				break;
			} else {
				str[i++] = 'a' + (c % alpha);
			}
		}
		str[substr_maxlen] = '\0';
	} else {
		i = other_substr = rand() % idx;
		while (strlen(test->substrings[other_substr % idx]) >= substr_maxlen &&
				i + idx > other_substr) {
			other_substr++;
		}
		assert(strlen(test->substrings[other_substr % idx]) == substr_maxlen && i + idx == other_substr ||
				strlen(test->substrings[other_substr % idx]) < substr_maxlen);
		if (i + idx == other_substr) {
			strcpy(str, test->substrings[i]);
			/* 'i' has experienced an identity crisis here */
			i = strlen(str);
			if (ss_type != 3) {
				app = gen_new_substr(chance, substr_maxlen - i, alpha, test, -1, 0);
				if (ss_type == 1) {
					strcat(str, app);
					free(app);
				} else if (ss_type == 2) {
					app = realloc(app, strlen(app) + strlen(str) + 2UL);
					strcat(app, str);
					free(str);
					str = app;
				}
			} else {
				app = gen_new_substr(chance, (substr_maxlen - i) / 2, alpha, NULL, -1, 0);
				memmove(str + (substr_maxlen - i) / 2, str, i);
				memmove(str, app, strlen(app));
				free(app);
				app = gen_new_substr(chance, (substr_maxlen - i + 1) / 2, alpha, NULL, -1, 0);
				strcat(str, app);
				free(app);
			}
		} else {
			/* can't do it, giving up */
			free(str);
			/*
			fprintf(stderr, "failed to include a substring into a substring (ss_type=%d)\n",
					ss_type);
			 */
			return gen_new_substr(chance, substr_maxlen, alpha, test, idx, 0);
		}
	}

	return str;
}

/**
 */
struct testdata *
generate_test(const int seed, const int alpha, const int substr_count,
		int substr_maxlen, const int chance, const int text_len,
		const int ss_type_weights[5], const int substr_incl)
{
#define STW ss_type_weights
	register int i, j;
	struct testdata *test;
	int c;
	int *hash;
	int *slen;
	int ss_type = 0;

	/*
	 * ss_type: 0 - random
	 *          1 - substr1 .. random
	 *          2 - random .. substr1
	 *          3 - random .. substr1 .. random
	 */

	srand(seed);

	/* TODO: check arguments' sanity, fix if possible */
	while (alpha == 1 && substr_count >= substr_maxlen)
		substr_maxlen += 1;
	if (substr_maxlen < 1 || substr_maxlen > 100 || substr_count < 1 || substr_count > 5000 ||
			text_len < 0 || text_len > 1000000 || alpha < 1 || alpha > 26) {
		fprintf(stderr, "%s: bad test generator arguments\n", __func__);
		fprintf(stderr, "%s: seed=%d, alpha=%d, substr_count=%d, substr_maxlen=%d, chance=%d, "
				"text_len=%d, STW={ %d, %d, %d, %d, %d }, substr_incl=%d\n",
				__func__, seed, alpha, substr_count, substr_maxlen, chance,
				text_len, STW[0], STW[1], STW[2], STW[3], STW[4], substr_incl);
		return NULL;
	} else {
		fprintf(stdout, "generating test %d\n", seed);
	}

	test = malloc(sizeof *test);
	test->substr_count = substr_count;
	test->substrings = malloc(substr_count * sizeof *test->substrings);
	hash = calloc(substr_count, sizeof *hash);
	slen = calloc(substr_count, sizeof *slen);

	i = 0;
	while (i < substr_count) {
		if (i > 1) {
			ss_type = 4;
			c = rand() % STW[4];

			switch ((c < STW[0]) + (c < STW[1]) + (c < STW[2]) + (c < STW[3])) {
			case 0:
				fputs("no way..\n", stderr);
			case 1: ss_type--;
			case 2: ss_type--;
			case 3: ss_type--;
			case 4: ss_type--;
				break;
			default:
				fputs("something's weird\n", stderr);
			}
		} else {
			ss_type = 0;
		}

		test->substrings[i] = gen_new_substr(chance, substr_maxlen, alpha,
				test, i, ss_type);
		slen[i] = strlen(test->substrings[i]);
		hash[i] = string_hash(test->substrings[i], alpha);

		/*
		 * check for identical strings
		 */
		j = 0;
		while (j < i) {
			if (hash[i] == hash[j] &&
					strcmp(test->substrings[i], test->substrings[j]) == 0) {
				free(test->substrings[i]);
				test->substrings[i] = gen_new_substr(chance, substr_maxlen, alpha,
						test, i, 0);
				slen[i] = strlen(test->substrings[i]);
				hash[i] = string_hash(test->substrings[i], alpha);
				j = 0;
			} else {
				j++;
			}
		}

		i++;
	}

	free(hash);

	/*
	 * Text
	 */
	test->text = malloc(1UL + text_len);
	test->text_len = text_len;
	i = 0;
	while (i < text_len) {
		/* XXX */
		if (substr_incl > 0 && rand() % substr_incl == 0) {
			c = j = rand() % substr_count;
			while (c + substr_count < j && slen[j % substr_count] + i > text_len)
				j++;
			j %= substr_count;

			if (slen[j] + i <= text_len)
				strcpy(test->text + i, test->substrings[j]);
		} else {
			test->text[i++] = 'a' + rand() % alpha;
		}
	}
	test->text[i] = '\0';
	test->text_len = strlen(test->text);

	free(slen);

	return test;
#undef STW
}

void
fprint_test(struct testdata *test, FILE *fp)
{
	int i;

	if (fp == NULL)
		return;
	if (test == NULL || test->substr_count <= 0) {
		fputs("<empty>\n", fp);
		return;
	}

	fprintf(fp, "%d\n", test->substr_count);
	for (i = 0; i < test->substr_count; i++) {
		fputs(test->substrings[i], fp);
		fputc('\n', fp);
	}
	fputs(test->text, fp);
	fputc('\n', fp);
}

void
free_test(struct testdata *test)
{
	int i;

	if (test == NULL)
		return;

	for (i = 0; i < test->substr_count; i++)
		free(test->substrings[i]);
	free(test->substrings);
	free(test->text);
	free(test);
}

int
main(int argc, char **argv)
{
	static struct testdata *alltests[SMALLTESTS + LARGETESTS];
	struct testdata *test;
	const int allrandom[] = { 1, 1, 1, 1, 1 },
	          mostlyrandom[] = { 7, 8, 9, 10, 10 },
			  equal[] = { 1, 2, 3, 4, 4 },
			  lotsofincl[] = { 10, 40, 70, 100, 100 },
			  _IQtest[] = { 1, 2, 3, 4, 16 };
	int i;
	FILE *fp;
	char filename[32];

	srand(1);
	test = malloc(sizeof *test);
	test->substr_count = 4;
	test->substrings = calloc(100, sizeof test->substrings[0]);
	test->substrings[0] = strdup("he");
	test->substrings[1] = strdup("lo");
	test->substrings[2] = strdup("hello");
	test->substrings[3] = strdup("low");
	test->text = strdup("helloworld");
	alltests[0] = test;

	/* a complete testcase */
	alltests[1] = test = malloc(sizeof *test);
	test->substrings = calloc(40, sizeof *test->substrings);
	test->substrings[0] = strdup("aa");
	test->substrings[1] = strdup("aaa");
	test->substrings[2] = strdup("a");
	test->substrings[3] = strdup("b");
	test->substrings[4] = strdup("aba");
	test->substrings[5] = strdup("aaba");
	test->substrings[6] = strdup("ba");
	test->substrings[7] = strdup("aaab");
	test->substrings[8] = strdup("abababa");
	test->substr_count = 9;
	test->text = gen_new_substr(0, 100, 2, NULL, 0, 0);

	alltests[2] = generate_test(1, 7, 10, 15, 500, (rand() % 40) + 20, mostlyrandom, 3);

	for (i = 3; i < SMALLTESTS; i++) {
		alltests[i] = generate_test(i, (rand() % 12) + 1, (rand() % 7) + 1, (rand() % 10) + 5,
				500, 4 * (rand() % 3) + 2 * (rand() % 3) + (rand() % 3) + 1, mostlyrandom, (rand() % 7) + 2);
	}
	while (i < SMALLTESTS + LARGETESTS - 5) {
		alltests[i] = generate_test(i, (rand() % 11) + 16, (rand() % 4901) + 100,
				(rand() % 51) + 50, 10, (rand() % 1000000) + 1,
				lotsofincl, 20);
		i++;
	}
	/* long random substrings, text completely consists of substrings */
	alltests[SMALLTESTS + LARGETESTS - 5] = generate_test(SMALLTESTS + LARGETESTS - 5, 26, 5000,
			100, 0, 1000000, allrandom, 1000);

	/* long random substrings, text completely random */
	alltests[SMALLTESTS + LARGETESTS - 4] = generate_test(SMALLTESTS + LARGETESTS - 4, 26, 5000,
			100, 1, 1000000, allrandom, 0);

	/* shorter substrings including one another, text sometimes inlcudes substrings
	 * (5% probability on every symbol) */
	alltests[SMALLTESTS + LARGETESTS - 3] = generate_test(SMALLTESTS + LARGETESTS - 3, 26, 5000,
			100, 100, 1000000, equal, 20);

	/* "extreme" tests:
	 * alphabet consists of only 'a' and 'b', long random substrings, text
	 * sometimes includes substrings (10% chance on every symbol) */
	alltests[SMALLTESTS + LARGETESTS - 2] = generate_test(SMALLTESTS + LARGETESTS - 2, 2, 5000,
			100, 1, 1000000, allrandom, 10);

	/* "killer test": 2 letters, shortest substrings, 25% chance of substring
	 * inclusion at every symbol of the text (although, random text would work
	 * just as fine) */
	alltests[SMALLTESTS + LARGETESTS - 1] = generate_test(SMALLTESTS + LARGETESTS - 1, 2, 5000,
			100, 600, 1000000, lotsofincl, 4);

	for (i = 0; i < SMALLTESTS + LARGETESTS; i++) {
		snprintf(filename, sizeof filename, "%02d.txt", i + 1);
		fp = fopen(filename, "w+t");
		if (fp == NULL) {
			fprintf(stderr, "Failed to open file \"%s\" for R/W, skipping\n", filename);
		} else {
			fprint_test(alltests[i], fp);
		}
		fflush(fp);
		fclose(fp);
		fprintf(stderr, "finished test \"%s\"\n", filename);
		usleep(1000U);
	}
	for (i = 0; i < SMALLTESTS + LARGETESTS; i++)
		free_test(alltests[i]);

	return 0;
}
